﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace _07.ShortestPathWeightedDirectedGraph
{
    class Graph
    {
        private IDictionary<int, int>[] childNodes;

        public Graph(IDictionary<int, int>[] childNodes)
        {
            this.childNodes = childNodes;
        }

        public int NodesCount
        {
            get { return childNodes.Length; }
        }

        public void FindShortestPaths(int startNode)
        {
            int[] distances = new int[childNodes.Length];
            int[] previous = new int[childNodes.Length];
            HashSet<int> nodes = new HashSet<int>();
            
            for (int i = 0; i < childNodes.Length; i++)
            {
                nodes.Add(i);
                previous[i] = int.MinValue;
                if (i != startNode)
                {
                    distances[i] = int.MaxValue;
                }
                else
                {
                    distances[i] = 0;
                }
            }

            distances = CalculatePaths(nodes, distances, previous);

            for (int i = 0; i < distances.Length; i++)
            {
                Console.WriteLine("{0} - {1}", i, distances[i]);
            }
        }
  
        private int[] CalculatePaths(HashSet<int> nodes, int[] distances, int[] previous)
        {
            while (nodes.Count > 0)
            {
                int node = GetNextNode(distances, nodes);
                if (node == int.MaxValue)
                {
                    break;
                }

                nodes.Remove(node);

                foreach (var child in childNodes[node])
                {
                    if (nodes.Contains(child.Key))
                    {
                        int newDistance = distances[node] + child.Value;
                        if (newDistance < distances[child.Key])
                        {
                            distances[child.Key] = newDistance;
                            previous[child.Key] = node;
                        }
                    }
                }
            }

            return distances;
        }

        private int GetNextNode(int[] distances, HashSet<int> nodes)
        {
            int min = int.MaxValue;
            int next = int.MaxValue;

            foreach (var node in nodes)
            {
                if (distances[node] < min)
                {
                    min = distances[node];
                    next = node;
                }
            }

            return next;
        }
    }
}
